#include <cassert>
#include <limits>

#include "binary_search.h"

namespace ads {
// O(log n) where n = (h - l) + 1 [h and l of the first call]
int BinarySearch::nearest(int *a, int l, int h, int x) {
  assert(a);
  int smallest_diff = std::numeric_limits<int>::max();
  int smallest_index = -1;

  while (l <= h) {
    int m = (l + h) / 2;
    
    int diff = abs(a[m] - x);
    if (diff == 0) {
      return m;
    } else {
      if (diff < smallest_diff) {
        smallest_diff = diff;
        smallest_index = m;
      }
      if (x < a[m]) {
        h = m - 1;
      } else {
        l = m + 1;
      }
    }
  }
  
  return smallest_index;
}
}  // end of namespace
